package classify.DFS;

import object.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次.
 *
 * 因发明「深度优先搜索算法」，约翰 · 霍普克洛夫特与罗伯特 · 塔扬在1986年共同获得计算机领域的最高奖：图灵奖。
 * @author sps
 * @date 2023/5/19 16:37
 */
public class depthFirstSearch {

    int pre, count, maxCount;
    List<Integer> answer = new ArrayList<Integer>();
    public int[] findMode(TreeNode root) {
        dfsMode(root);
        int[] res = new int[answer.size()];
        for(int i=0; i<answer.size(); i++){
            res[i] = answer.get(i);
        }
        return res;
    }

    private void dfsMode(TreeNode root) {
        if(root == null)return;

        dfsMode(root.left);
        updateMode(root.val);
        dfsMode(root.right);
    }

    private void updateMode(int val) {
        if(pre == val){
            count++;
        }else {
            pre = val;
            count = 1;
        }
        if(count == maxCount){
            answer.add(val);
        }
        if(count > maxCount){
            answer.clear();
            answer.add(val);
        }
    }
}
